package elementary_alg.array;

import java.util.Map;

/**
 * @author : Kong Decheng
 * @date : 2021/04/02
 * @description: 有效的数独
 */
public class LC10 {
    /**
     * 遍历该 9x9 数独三次，以确保：
     * 行中没有重复的数字
     * 列中没有重复的数字
     * 3x3子数独内没有重复的数字
     * 枚举子数独：box_index = (row / 3) * 3 + columns / 3
     * 确保行列子数独中没有重复项：
     * 可以利用 value -> count 哈希映射来跟踪所有已经遇到的值。
     *
     * @param board
     * @return
     */
    public boolean solution_1(char[][] board) {

        int length = board.length;
        // line[0][3] 表示第 1 行是否有数字3
        // 0 表示没有，1 表示有
        int[][] line = new int[length][length];
        int[][] column = new int[length][length];
        int[][] boxes = new int[length][length];


        // 遍历数独
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {

                if (board[i][j] == '.') {
                    continue;
                }
                // 当前格子中的数字，这里减一是因为数组索引是从 0 开始的
                int num = board[i][j] - '0' - 1;
                // 子数独索引
                int box_index = i / 3 * 3 + j / 3;
                // 检查每个单元格值是否已经在当前的行/列/子数独中出现过
                // 如果出现重复，返回 false
                if (line[i][num] != 0 || column[j][num] != 0 || boxes[box_index][num] != 0) {
                    return false;
                }
                // 如果没有，则保留此值以进行进一步跟踪
                // 例如: line[0][7]=column[2][7]=boxes[0][7]=1
                // 第一行有 8，第 3 列有 8，第一个子数独有 8
                line[i][num] = column[j][num] = boxes[box_index][num] = 1;
            }
        }
        return true;
    }
}
